package es.analisis.algoritmos;

class Algoritmos {

    private static double mejorValor = 0;
//    private static int k = 0;
    private static      ListaObjetos copia;
    public static int greedy(ListaObjetos lista) {
        int pesoActual = 0; // Peso de los objetos que hay dentro de la mochila
        int valorActual = 0; // Valor de los objetos que hay en la mochila

        //	int i = 0;
        for (Objeto o : lista.getLista()) {
            //pesoActual += o.getPeso();
            if ((pesoActual + o.getPeso()) <= lista.getPesoMax()) {
                valorActual += o.getValor();
                pesoActual += o.getPeso();
            }
        }
        return valorActual;
    }

    public static int progDinamica(ListaObjetos lista) {
        int n = lista.tam();
        int pesoMax = lista.getPesoMax();

        int[][] tabla = new int[n + 1][pesoMax + 1];

        // Inicializamos la primera fila y columna de la tabla a 0
        for (int i = 1; i <= n; i++) {
            tabla[i][0] = 0;
        }

        for (int j = 0; j <= pesoMax; j++) {
            tabla[0][j] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= pesoMax; j++) {
                if (j < lista.getLista().get(i - 1).getPeso()) {
                    tabla[i][j] = tabla[i - 1][j];
                } else {
                    if (tabla[i - 1][j] > tabla[i - 1][j - lista.getLista().get(i - 1).getPeso()] + lista.getLista().get(i - 1).getValor()) {
                        tabla[i][j] = tabla[i - 1][j];
                    } else {
                        tabla[i][j] = tabla[i - 1][j - lista.getLista().get(i - 1).getPeso()] + lista.getLista().get(i - 1).getValor();
                    }
                }
            }
        }


        return tabla[n][pesoMax];
    }

    // Comprueba si el peso de los k primeros objetos introducidos es menor que el peso maximo que podemos meter
    private static boolean EsFactible(int k, ListaObjetos lista) {
        int peso = 0;

        for (int i = 0; i <= k; i++) {
            if (lista.getLista().get(i).getEnMochila() == 1) {
                peso += lista.getLista().get(i).getPeso();
            }
        }

        return peso <= lista.getPesoMax();
    }

    // Valor de los objetos actualmente en la mochila para el metodo de Ramificacion y poda
    private static int Valor(ListaObjetos lista, int k) {
        int valor = 0;

        for (int i = 0; i <= k; i++) {
            if (lista.getLista().get(i).getEnMochila() == 1) {
                valor += lista.getLista().get(i).getValor();
            }
        }
        return valor;
    }

    // Metodo para calcular la cota
    private static double cota(int k, ListaObjetos lista) {
        double cota = 0,
            valorEnMochila = 0,
            pesoEnMochila = 0,
            pesoRestante = 0,
            cocientePeso= 0,
            producto = 0;

        for(int i = 0; i <= k; i++){
            valorEnMochila += lista.getLista().get(i).getValor() * lista.getLista().get(i).getEnMochila();
        }

        for (int i = 0; i <= k; i++) {
            pesoEnMochila += lista.getLista().get(i).getPeso() * lista.getLista().get(i).getEnMochila();
        }
        pesoRestante = lista.getPesoMax() - pesoEnMochila;

        cocientePeso = pesoRestante / lista.getLista().get(k).getPeso();
        producto = cocientePeso * lista.getLista().get(k).getValor();
        cota = valorEnMochila + producto;
        return cota;
    }


    private static void KSBackRec(int k, ListaObjetos lista){
        double cota, valor;


        for(int pos = 0; pos <= 1; pos++) {
            lista.getLista().get(k).setEnMochila(pos);

            boolean factible = EsFactible(k ,lista);
            if(factible){

                if(k == lista.tam() -1){
                    valor = Valor(lista, k);
                    if(valor > mejorValor) {
                        copia = lista.copiar();
                        mejorValor = valor;
                        System.out.println("MejorValor en if: "+mejorValor);
                    }
                }else{
                    cota = cota(k,lista);
                    if(cota > mejorValor) {
                       //mejorValor = Valor(lista, k);
                       // mejorValor = cota;
                       // k = k + 1;
                        //copia = lista;
                    System.out.println("MejorValor antes de recursividad: "+mejorValor);
                        KSBackRec(k+1, lista);
                    }
                }
            }
        }
    }

    public static double KSBack(ListaObjetos lista) {
        System.out.println(lista.toString());
        mejorValor = 0;

        KSBackRec(0, lista);
        System.out.println(copia.toString());
        return mejorValor;
    }
}